package com.cqs.leetcode.dp;

import java.util.HashMap;
import java.util.Map;

/**
 * lixw
 * 2023/10/24
 */
public class Solution1155 {
    private final static int MOD = (int) Math.pow(10, 9) + 7; // < Integer.MAX_VALUE/2

    public int numRollsToTarget(int n, int k, int target) {
        Map<Integer, Integer> cache = new HashMap<>();
        return numRollsToTarget0(n, k, target, cache);
    }


    public int numRollsToTarget0(int n, int k, int target, Map<Integer, Integer> cache) {
        int tmp = n * k;
        if (target >= tmp || target < n) {
            return tmp == target ? 1 : 0;
        }
        //30, 30, 1000
        int key = n * 300001 + k * 1001 + target;
        Integer val = cache.get(key);
        if (val != null) {
            return val;
        }
        int sum = 0;
        for (int i = 1; i < k + 1; i++) {
            sum = (sum + numRollsToTarget0(n - 1, k, target - i, cache)) % MOD;
        }
        cache.put(key, sum);
        //System.out.println(n + "\t" + k + " " + target +" " + sum);
        return sum;
    }

}
